Games of Daze

home *** CD-ROM | disk | FTP | other *** search

/ Games of Daze / Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso / x2ftp / msdos / math / fixfloa2 / fixfloat.doc < prev next >

Wrap

Text File | 1995-03-26 | 25.1 KB | 867 lines

FIX-FLOAT =========== A LIBRARY FOR RAPID HANDLING OF DECIMAL NUMBERS REPRESENTED ON A FIXED POINT BINARY NOTATION + 32 bit inexhaustible ??? random number generator ------------- | Version 1.2 | ------------- REQUIREMENTS : ============== The routines are written to be run in protected mode with 32 bit default data size. A C - compiler is required to set up data structures, this could be done in any highlevel language that can export symbols visible to assembly language. C++ uses a strange naming convention of their symbols making the task more difficult. Support of floating point processing is also required to setup data structures. No 486 or higher instructions are used, a 386 is required however. All timings given in the function descriptions below are based on Intels 486. INTRODUCTION : ============== Fixfloat is a small library for handling decimal numbers represented on a fixed point number format. A decimal number is represented with 32 bits, using the upper 16 bits as the integral part and the lower 16 bits as the decimal part : 31 24 16 8 0 ( bit nr ) ________ ________ ________ ________ register : |________|________|________|________| integral part ^ decimal part A few decimal numbers and their hexadecimal representation as fixfloats: Decimal number | Fixfloat (hex) --------------------------------- 1/16 | 0000 1000h 0.25 | 0000 4000h 0.5 | 0000 8000h 1 | 0001 0000h 7.1875 | 0007 1000h In C language conversion from floats & doubles to fixfloats is performed by multiplying by 65536 and taking the integral part of this result. ADVANTAGES & DISADVANTAGES : ============================ The advantage of this representation of decimal numbers are that calculations are quicker, usually by a factor 1.5 to 4, compared to using floating point instructions, the process of converting to an integer is quick & simple ( 'shr eax,16' if eax contains a fixfloat in assembler, (a>>16) in C if 'a' is a fixfloat ). Converting from floatingpoint register to integer takes 33 clockcycles on a 486, it takes 2 clock cycles to go from fixfloat to integer. Another advantage is that software using this format performs equally whether there is an FPU available or not. This remains an argument since many new x86 processors of various brands ships without floating point unit. Adding and subtracting operations use standard add & sub instructions and computes 24 times faster than the fpu equivalents. The primary disadvantage of this format is of course that the range of the numbers is limited to -32768 to 32767. Other disadvantages are that precision is limited and that for most operations a subroutine call is required with added time for call & ret instructions. This can be undone by expanding the function into the calling body. These routines are not aimed towards applications where the result is numerically presented to the user but rather where there is no need for better precision than a 4-5 decimal digits. Another disadvantage is that multiplications are relatively slow on the integer unit compared to the floating point unit, this is true for both 486 & 586 processors. ALGORITHMS : ============ Divisions and multiplications are performed by unsigned integer machine instructions, using the 64 bit results of multiplication and the possibility to use 64 bits in division denominators. No precision or time is lost in this way. The trancendental functions supported are usually performed by a number of shifts to get the in value in an appropriate range and then looking in a data table and some shifting of the result. Precision is limited by how large data tables one wants. Typically 12 bits precision of the incoming value is supported but this is easily modified. TRIGONOMETRY : ============== The anglesum of a circle is 65536 instead of 2 PI, thus a circle have angles from 0 to 1. Here are some angles on different angle bases : DEG | RAD | FIXFLOAT =========================== 45 | PI/4 | 02000h 90 | PI/2 | 04000h 180 | PI | 08000h 360 | 2PI | 10000h Sin & cos functions have 16384 steps on a circle, the asin, acos functions goes from 0 to 1 in 4096 steps. The tan function goes from zero to 90 degrees in 1024 steps, if angles are larger than 84.375 degrees a separate 256 entry table is used and if angles are larger than 88.59375 a last 256 entry table is used. The atan functions uses a table of 1024 entries if argument is less than 4 ( 0-4/1024 ). If argument is less than 16 it uses a table of 256 entries ( 0-16/256 ) if argument is less than 512 it uses a table of 256 entries ( 0-512/256 ), if argument is less than 8192 it uses a table of 256 entries ( 0-8192/ 256). COMBINED ARITHMETIC FUNCTIONS : =============================== By squaring a number larger than 256 the 16 bit integral part overflows. By combining a few actions in a function one can sometimes benefit from the 64 bit intermediate format. This is used by functions ffhyp, fftrihyp. The operations performed by ffhyp & fftrihyp are : ffhyp = sqrt ( a*a+b*b ) fftrihyp = sqrt ( a*a+b*b+c*c ) It is also possible to eliminate intermediate shifts if both divison and multiplication is performed. This is used in following operations : a * b a * b ffmuldiv = ------- ffmmd = ------- c * d c DATA TABLES : ================ The gen_fix_float_tables() function will setup the data tables needed by the trancemdental functions. A table is also setup for a random number generator. This function assumes that the compiler environment has some sort of support for double numbers and elementary trancendental functions. A random number generator must be present also. The rand function is expected to return a random number covering at least bits 0-14 (15 bits). At current the data tables occupies approximately 64 kb. The random table stands for 16 of those. Only the pure mul & div functions can be used without intializing data tables. It seems that it takes something like a second to intialize all tables. BASIC ARITHMETIC OPERATIONS, C LANGUAGE : ========================================== The file fixfloat.asm will have to be included in the project. In C-files using fixfloat functions the file "fixfloat.h" should be included by '#include "fixfloat.h"' statement. If other than mult / div functions are used the file cfifloa.c must be included in the project and the function gen_fixfloat_table() must be called before using any of the transcendental functions. Suppose we want to express 3.1415 & 2.7182 as a fixfloats in C. How do we do ? // Assign example float e; long a,b; a = 3.1415 * 65536; // The precompiler will take care of the // floatingpoint operator. a is now e = 2.7182; // fixfloat representation of 3.1415 b = e * 65536; // The floating point hardware or functiom // or emulator will take care of multiplication. // b now holds fixfloat representation of 2.7182 Suppose we've been doing some operations on a fixfloat quantity and want the integer part of it : long a, int_part; // code // a holds fixfloat number and we want integer part to be placed // in int_part : int_part = a>>16; Addition & Subtraction: // Addition demo long a,b,c; // declare three 32 bit quantities a = 8.7 * 65536; b = 2.2 * 65536; c = a + b; // add & put in c ( c holding 10.9 as fixfloat quantity ) Multiplication : To multiply fixfloat numbers from C one can use functions or inline assembly functions . The inline version is approx 8 cycles faster. // Inline signed multiply demo: #include "fixfloat.h" void main(){ long a,b,c; a = 3.3 * 65536; b = -3.0 * 65536; c = iffsmul(a,b); // c will hold the number -9.9 in fixfloat form. } // Unsigned multiply demo ( calls Asm function ): #include "fixfloat.h" void main(){ long a,b,c; a = 3.3 * 65536; b = 1000.0 * 65536; c = ffmul(a,b); // c will hold the number 3300 in fixfloat form. } To help renember name of functions, let's decode 'iffsmul' : i - stands for inline assmebly version, ff - stands for fixfloat, s - stands for signed ( can use negative numbers ) mul - stands for multiplication HINT : To have faster multiplications, if you know which value is the lower one, pass it as the 2nd argument, since multiplication happens bitwise and stops when all remaining bits are 0. Division : To divide fixfloat numbers from C one can use functions or inline assembly functions . The function version (ffdiv, ffsdiv) checks it's arguments to see if a divide overflow would occur, in this case the biggest possible number is returned, otherwise the division is performed. The inline versions does no argument checking and might raise exceptions. // Inline signed divide demo: #include "fixfloat.h" void main(){ long a,b,c; a = 15.5 * 65536; b = -5.0 * 65536; c = iffsdiv(a,b); // c will hold the number -3.1 in fixfloat form. } // Unsigned divide demo ( calls Asm function ): #include "fixfloat.h" void main(){ long a,b,c; a = 10.0 * 65536; b = 4.0 * 65536; c = ffdiv(a,b); // c will hold the number 2.5 in fixfloat form. } BASIC ARITHMETIC OPERATIONS, ASM LANGUAGE : ============================================ The file fixfloat.inc will have to be included in the .asm files using fixfloat functions. In your project 'fixfloat.asm' must be present. Fixfloats use 32 bits to represent themselves so full registers (EAX, EBX ...) should be used. Any 4 byte memory location stores them. The C- function gen_fixfloat_tables must be called before using other than mult / div functions. Addition & subtraction : Addition & subtraction works with std x86 add & sub operators: ; Addition demo mov eax,8.7 * 65536 mov ebx,2.2 * 65536 add ebx,eax ; ebx will now hold 10.9 in fixfloat notation Multiplication : There are two ways to multiply fixfloats from within asm. One can either call a function to do it or use a macro. The macro version will be typically 8 clocks faster. ; Macro signed multiply example : mov eax,3.3 * 65536 mov ebx,-3.0 * 65536 MFFSMUL ebx ; eax will now hold -9.9 in fixfloat form. ; NOTE edx will be modified by this macro !!! ; Unsigned multiply by function call example mov eax,3.3 * 65536 mov edx,1000.0 * 65536 call _ffmul ; eax will now hold 3300.0 in fixfloat form. ; NOTE edx will be modified by this function ! Division : There are two ways to divide fixfloats from within asm. One can either call a function to do it or use a macro. The function version (_ffdiv, _ffsdiv) checks it's arguments to see if a divide overflow would occur, in this case the biggest possible number is returned, otherwise the division is performed. The inline versions does no argument checking and might raise exceptions. ; Macro signed division example : mov eax,15.5 * 65536 mov ebx,-5 * 65536 MFFSDIV ebx ; eax will now hold -3.1 in fixfloat form ; NOTE edx will be modified by this macro !!! ; unsigned divide by function call example : mov eax,10.0 * 65536 mov ebx,4.0 * 65536 call _ffdiv ; eax will contain 2.5 in fixfloat form. ; NOTE edx will be modified by this function !!! GENERAL INFO ON FUNCTIONS : =========================== I have tried clocking a few of the functions using a hires timer but the results are inconsistent and I don't want to put too much effort into it. Most instructions in the funtions execute in one clock, except for shifts (2-4), multiplications (13-42), divisions (40), 16 bits loads (2). This is true for a 486 processor, for a 586 the situation is different again. AGI stalls have been avoided to a large extent. I have added time for loading data from math tables since this data at most times won't be in the primary cache. For a 16 bit load ( which is frequently usde to lessen table size ) with a 'eax*2' offset I have counted 7 clocks. None of the functions use any local or global variables, a few uses some stackspace (max 32 bytes). The timings mentioned below are based on instruction count and do not include the call and the ret statement. If called from C the names below should be used, if called from within assembly language a underbar must be added to end of functionname ( Watcom Std ). Parameters to the functions are used in the following order : eax - first argument edx - second argument ebx - third argument ecx - fourth argument Return values are in eax for all functions. For inline usage of multiply & divide, see section BASIC OPERATIONS, C LANGUAGE. For MACRO usage of multiply & divide, see section BASIC OPERATIONS, ASM LANGUAGE. DESCRIPTION OF FIXFLOAT FUNCTIONS : =================================== gen_fixfloat_tables : --------------------- Will calculate all the tables needed by below functions, should be called when using other first of all when using other functions than pure mul and div functions. Clocks : approx20 000 000 fftoa(long ff, char *buf) : --------------------------- Converts fixfloat ff to ascii decimal representation, puts result where buf points. Zero truncated format, 3.25 represented by '3.25'. fftoah(long ff, char *buf) : --------------------------- Converts fixfloat ff to ascii hexadecimal representation, puts result where buf points. Full format, 3.25 represented by '0003.4000'. ffsmul : -------- Multiplies the fixfloat in eax by the fixfloat in edx. Result in eax. The result has sign according to the factors. This function consists of only 2 instructions and is therefore good to expand into calling body : imul edx ; these two instructions does the job shrd eax,edx,16 Affects : edx Clocks : 20 - 45 ffsdiv : -------- Divides the fixfloat in eax by the fixfloat in edx. Result in eax. Guards against the situation where the result doesn't fit into 32 bits. max positive number or max negative number is then returned. Thus the function cannot generate any division by 0 error. 0/0 will also return 07FFF.FFFF. The result has sign according to the nominator & denominator. Affects : none Clocks : 73 NOTE : When certain that the result will fit into 32 bits use iffsdiv in from C or macro MFFSDIV from Asm. This will gain approx 20 cycles. NOTE : Divisions are quite a bit slower than multiplications, if performing many divisions by the same number x it might be good to divide 1 by x and then multiply by this. ffmul : ------- Unsigned multiplication by two fixfloats, eax and edx. Result in eax. This function consists of only 2 instructions and is therefore good to expand into calling body : mul edx ; these two instructions does the job shrd eax,edx,16 Affects : edx Clocks : 20 - 45 ffdiv : ------- Unsigned division between two fixfloats, eax and edx, result in eax. Checking as ffsdiv. Affects : none Clocks : 50 NOTE When certain that the result will fit into 32 bits use iffdiv in from C or macro MFFDIV from Asm. ffsin : ------- eax contains angle to take sinus from. Value returned in eax. Affects : none Clocks : 26 ffcos : ------- eax contains angle to take cosinus from. Value returned in eax. Affects : none Clocks : 27 ffasin : ------- eax contains angle to take arcsinus from. Value returned in eax. Affects : none Clocks : 21 ffacos : ------- eax contains angle to take arccosinus from. Value returned in eax. Affects : none Clocks : 23 fftan : ------- eax contains angle to take tan from. Value returned in eax. Affects : none Clocks : 23 - 33 ffatan : ------- eax contains angle to make angle from. Value returned in eax. Affects : none Clocks : 25 - 38 ff_vec_to_ang : -------------- Expresses the direction of a vector in fixfloat degrees. eax contains the x component of the vector and edx the y component of the vector. A result of zero indicates a vector pointing to the left, a result of 16384 indicates a vector pointing straight up, a result of 32768 indicates a vector pointing to the right. The function has a resolution of 8192 steps around the unit circle. eax - x component of vector edx - y component of vector returns angle in eax Affects : none Clocks : approx 150 fflog2 : -------- eax contains fixfloat to tak 2logarithm on. Value returned in eax. Affects : none Clocks : 56 ffexp2 : -------- eax contains the number to raise 2 to. Value returned in eax. Affects : none Clocks : 20 ffpow : ------- eax contains base and edx contains exponent. Value returned in eax. This function is a combination of fflog2, ffsmul, ffexp2. Affects : none Clocks : 152 ffsqrt: ------- eax contains value to take square root of, returns squareroot in eax. Affects : none Clocks : 61 ffhyp : ------- Used to calculate hypothenuse of triangle. eax contains one side, edx the other one. Result is returned in eax. An intermediate result larger than 32 bits will not overflow, this is the advantage compared to performing the operation step by step. returns sqrt ( a*a + b*b) Affects : none Clocks : 168 ffalmosthyp: ------------ Used to calculate an approximation to the hypothenuse of a triangle. eax contains the length of one side, edx the other. If given a negative argument it makes it positive before using. It works by adding half of the smaller value to the bugger and returning it. To be such a simple approximation it gives a surprisingly good result. Affects : none Clocks : 18 fftrihyp : ---------- As above but takes three arguments, the third is squared and added to the two first ones. returns sqrt ( a*a + b*b + c*c) Affects : none Clocks : 212 ffmuldiv : ---------- Given four fixfloats a,b,c,d in register eax,ebx,ecx,edx it will calculate (a * d) / (b*c) . This guards agains intermediate over- flows and saves a bit of time. Returns +/- infinity if 0 in denominator. Affects : none Clocks : 150 ffmmd : ------- Given three fixfloats in eax,edx,ebx it will calculate (eax*edx)/ebx allowing for more than 32 bit intermediate result. Returns +/- infinity if 0 in denominator. Affects : none Clocks : 94 ffortproj : ----------- The function is short for 'ortogonal projection', it is used for finding out how much a vector travels in another vectors direction. If it is perpendicular to the other vector 0 is returned, if it travels the same distance in the other vectors direction as the length of the other vector 1 is returned. Negative meaning it goes in opposite direction and a number above one that it goes further than the other vector in its direction. This function uses shifting (5 steps right ) to keep result within format. Be aware ! Vector (b,d) is projected onto (a,c) : eax - a ( two vectors (a,c) , (b,d) ) edx - b ebx - c ecx - d returns (a*b+c*d)/(a*a+c*c) Affects : none Clocks : A lot :) ffortproj1 : ----------- Same as above function but it takes square root of denominator before dividing, therefore it returns the length travelled in the other vectors direction. This is what is usually meant by ortogonal projection. This function uses shifting (5 steps right ) to keep result within format. Be aware ! Vector (b,d) is projected onto (a,c): eax - a ( two vectors (a,c) , (b,d) ) edx - b ebx - c ecx - d returns (a*b+c*d)/sqrt(a*a+c*c) Affects : none Clocks : Uncountable ... ffdot_through_hyps : -------------------- Function does what the name says, having two vectors (a,c) & (b,d) it returns the dot product of the vectors through the product of the lengths of the vectors. This function uses shifting (5 steps right ) to keep result within format. Be aware ! eax - a edx - b ebx - c ecx - d returns (a*b+c*d)/(sqrt(a*a+c*c)*sqrt(b*b+d*d)) Affects : none Clocks : Many ... ff_solve_2nd_poly : ------------------- Functions finds the real roots of a 2:nd degree equation in the form : 2 x + px + q = 0 Arguments : eax - p edx - q ebx - pointer to long (conj ptr) ecx - pointer to long (pre_ptr) returns : 0 - success nonzero - couldn't find any real roots The roots of the polynomial will be : the contents of the pre_ptr +/- contents of conj_ptr Example : long p, q, conj, pre; long root1, root2; p = 2 * 65536; q = -3 * 65536; ff_solve_2nd_poly(p, q, &conj, &pre); root1 = pre + conj; // root 1 - 1.0 * 65536 root2 = pre - conj; // root 2 - -3.0 * 65536 NOTE When solving a square of p is used, no overflows will appear since the function uses 64 bit intermediate results. Affects : none Clocks : Approx 140 DESCRIPTION OF INTEGER FUNCTIONS : ================================== There is only one integer function ( taking integer as result, giving integer as result supported.) More may be added. isqrt : ------- Function returns a true square root of its arguement. It uses the same table as ffsqrt, therefore needs gen_fixfloat_tables init to work properly. A square root is always less than or equal to the actual square root, isqrt(15) = 3, isqrt(16) = 4 etc. Observe that precision of this one is not more than 3 digits. Affects : none Clocks : 58 DESCRIPTION OF RANDOM NUMBER FUNCTIONS : ======================================== The function rand32 is responsible for producing pseudo random numbers. The numbers are produced using a combination of a multiplication and a data table containing pregenerated numbers. 8 bits of the data table is used for each number, it takes 16384 times to step through it. The multiplicand is constant during one such run, then it is changed. The random table is also mutaded at this time. The number generated is always dependent on the previous one. Even if the same multiplicand reappears when restarting on a table it is highly unlikely that the product in that moment would be the same as the one 256 million times ago. If this would happen the same random numbers would only appear until a mutated entrance would occur, which would be the first to come. The period for the randomgenerator shold be : 16384 * 16384 * 2^32 * 2^(16384*32) = 2 ^ 524438 Which I think is enough for many applications. ( A DEC Alpha 330 MHz would produce 2^60 pseudo random numbers in 1000 years if dedicated to it. ) There are 3 memory locations visible affecting the generator : _rnd3 - contains the number by which to multiply the last random number. Before multiplication a constant is added and then the value is truncated to 12 bits to keep multiplication time down. _rnd2 - contains how many numbers generated so far. Every time it ticks over a 16 kb limit the _rnd3 is changed. _rnd1 - contains the last number generated. Any of these can be changed to produce 'randomize' affect. From a given start it will always produce identical numbers. rand32 : -------- Returns a 32 bit pseudo random number. Affects : none Clocks : 41 randinter : ----------- eax contains the number above the number desired. This functions computes the 'and' value before calling rand32 and is a bit slower. Example : // Want random number 0-19 long rn; rn = randinter(20); Affects : none Clocks : 77 - 124 ( Average c:a 110 ) randpowint : ------------ eax contains a number to 'and' the 32 bit random number with, edx contains the number above the maximum number desired. This function can be used when the interval of the randomnumber one want's is the same from time to time, saves something like 25 clocks. If an interval close to the 'and' value in eax is chosen it will have to loop back fewer times. Example : // Want random number 0-99 long rn; rn = randpowint(127,100) .... // Want random number 0-2999 long rn; rn = randpowint(4095,3000); Affects : none Clocks : 47 - 94 ( Average c:a 80 )